/**
 * 稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
 * <p>
 * 示例1:
 * <p>
 * 输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""],
 * s = "ta"
 * 输出：-1
 * 说明: 不存在返回-1。
 * <p>
 * <p>
 * 示例2:
 * <p>
 * 输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s
 * = "ball"
 * 输出：4
 * <p>
 * <p>
 * 提示:
 * <p>
 * <p>
 * words的长度在[1, 1000000]之间
 * <p>
 * <p>
 * Related Topics 数组 字符串 二分查找 👍 80 👎 0
 */


package com.xixi.basicAlgroithms.binarySearch;

public class ID_interview_10_05_SparseArraySearchLcci {
    public static void main(String[] args) {
        Solution solution = new ID_interview_10_05_SparseArraySearchLcci().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findString(String[] words, String s) {
            int len = words.length;
            int l = 0;
            int r = len - 1;
            while (l <= r) {
                while (l <= r && words[l].equals("")) l++;
                while (l <= r && words[r].equals("")) r--;
                int mid = l + (r - l) / 2;
                while (mid <= r && words[mid].equals("")) mid++;
//       while(mid>=l&&words[mid].equals("")) mid--;
                if (words[mid].compareTo(s) == 0) {
                    return mid;
                }
                if (words[mid].compareTo(s) > 0) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return -1;
        }
    }


//leetcode submit region end(Prohibit modification and deletion)


}